package main.Q801_900;

import java.util.*;

public class Q841_850 {
    public static void main(String[] args) {
        System.out.println("Question841：钥匙和房间");
        System.out.println("Question842：");
        System.out.println("Question843：");
        System.out.println("Question844：比较含退格的字符串");
        System.out.println("Question845：");
        System.out.println("Question846：一手顺子");
        System.out.println("Question847：");
        System.out.println("Question848：");
        System.out.println("Question849：");
        System.out.println("Question850：");
    }
}

class Question841 {
    public void process(boolean[] isValid, List<List<Integer>> rooms, int i) {
        if (isValid[i]) return;//当前房间已经打开
        Set<Integer> set = new HashSet<>(rooms.get(i));//获得该房间钥匙
        isValid[i] = true;//打开该房间
        for (int j : set) {
            process(isValid, rooms, j);//打开下一层的房间
        }
    }

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int length = rooms.size();
        boolean[] isValid = new boolean[length];
        isValid[0] = true;
        Set<Integer> set = new HashSet<>(rooms.get(0));
        for (int i : set) {
            process(isValid, rooms, i);
        }
        boolean result = true;
        for (boolean flag : isValid) result = result && flag;
        return result;
    }
}

class Question844 {
    public boolean backspaceCompare(String s, String t) {
        StringBuffer str1 = new StringBuffer(), str2 = new StringBuffer();
        char[] chars1 = s.toCharArray(), chars2 = t.toCharArray();
        for (int i = 0; i < chars1.length; i++) {
            if (str1.length() != 0 && chars1[i] == '#')
                str1.deleteCharAt(str1.length() - 1);//删除最后一个
            if (chars1[i] != '#') str1.append(chars1[i]);
        }
        for (int i = 0; i < chars2.length; i++) {
            if (str2.length() != 0 && chars2[i] == '#')
                str2.deleteCharAt(str2.length() - 1);
            if (chars2[i] != '#') str2.append(chars2[i]);
        }
        return str1.toString().equals(str2.toString());
    }
}

class Question846 {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        int n = hand.length;
        if (n % groupSize != 0) {
            return false;
        }
        Arrays.sort(hand);
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        for (int x : hand) {
            counts.put(x, counts.getOrDefault(x, 0) + 1);
        }
        for (int x : hand) {
            if (!counts.containsKey(x)) {
                continue;
            }
            for (int j = 0; j < groupSize; j++) {
                int num = x + j;
                if (!counts.containsKey(num)) {
                    return false;
                }
                counts.put(num, counts.get(num) - 1);
                if (counts.get(num) == 0) {
                    counts.remove(num);
                }
            }
        }
        return true;
    }
}